from cmath import inf
from typing import List


class Solution:
    """
    方法： maxSubArray
    逻辑: 使用动态规划思想，f表示以当前元素结尾的最大子数组和，遍历数组时不断更新f和全局最大值ans。

    Args:
        nums: List[int] - 整数数组

    Returns:
        int - 最大子数组和

    Time: O(n) - 只需要遍历数组一次

    Space: O(1) - 只使用了常数个变量
    """
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -inf
        f = 0
        for x in nums:
            f = max(f, 0) + x
            ans = max(ans, f)
        return ans
    
    """
    方法： maxSubArray1
    逻辑: 使用前缀和思想，通过维护最小前缀和来快速计算最大子数组和。

    Args:
        nums: List[int] - 整数数组

    Returns:
        int - 最大子数组和

    Time: O(n) - 只需要遍历数组一次

    Space: O(1) - 只使用了常数个变量
    """
    def maxSubArray1(self, nums: List[int]) -> int:
        ans = -inf
        min_pre_sum = pre_sum = 0
        for x in nums:
            pre_sum += x
            ans = max(ans, pre_sum - min_pre_sum)
            min_pre_sum = min(min_pre_sum, pre_sum)
        return ans